NOT NULL constraints are a ubiquitous tool for upholding data integrity. However, their performance benefits are less obvious. NOT NULL constraints provide a query optimizer with additional context that unlocks optimizations that significantly reduce query latency. In this post we’ll examine a few of these optimizations that transform query plans involving foreign key relationships.
Pushing limits into foreign-key joins
For a query that joins tables linked by a foreign key constraint, it can be beneficial to add NOT NULL constraints to the columns on the reference side of the foreign key relationship. This allows for hard limits to be pushed below a join operator in some cases, which can significantly reduce the number of rows scanned and joined, and reduce query latency. Consider the tables below with a foreign key constraint.
-- Create a parent table with 1000 rows, each ~4KB in size.
CREATE TABLE parent (
id UUID PRIMARY KEY,
t TEXT
);
INSERT INTO parent
SELECT gen_random_uuid(), repeat('p', 4096)
FROM generate_series(1, 1000);
-- Create 100 child rows for each parent row.
CREATE TABLE child (
id UUID PRIMARY KEY,
parent_id UUID REFERENCES parent(id)
);
INSERT INTO child
SELECT gen_random_uuid(), parent.id
FROM parent, generate_series(1, 100) g(i);
-- Collect table statistics.
ANALYZE parent;
ANALYZE child;
The query below fetches 5000 rows from the child table joined with their corresponding row in the parent table. Notice that the optimizer plans a full table scan over the child table, and applies the limit after the rows are joined. Also note that the execution time for this query was 33 milliseconds.
EXPLAIN ANALYZE
SELECT * FROM child JOIN parent
ON child.parent_id = parent.id
LIMIT 5000;
-- info
-- ------------------------------------------
-- planning time: 182µs
-- execution time: 33ms
--
-- • limit
-- │ count: 5000
-- │
-- └── • hash join
-- │ equality: (parent_id) = (id)
-- │ right cols are key
-- │
-- ├── • scan
-- │ table: child@child_pkey
-- │ spans: FULL SCAN
-- │
-- └── • scan
-- table: parent@parent_pkey
-- spans: FULL SCAN
Let’s add a NOT NULL constraint to child.parent_id.
ALTER TABLE child ALTER COLUMN parent_id SET NOT NULL;
The optimizer can now push the limit into the left side of the join, resulting in a much more efficient query plan. Notice that the scan over the child table is now a “LIMITED SCAN” that scans only 5000 rows. The query latency was less than a fifth of the previous query, taking only 6 milliseconds to execute.
EXPLAIN ANALYZE
SELECT * FROM child JOIN parent
ON child.parent_id = parent.id
LIMIT 5000;
-- info
-- ------------------------------------------
-- planning time: 152µs
-- execution time: 6ms
-- • hash join
-- │ equality: (parent_id) = (id)
-- │ right cols are key
-- │
-- ├── • scan
-- │ table: child@child_pkey
-- │ spans: LIMITED SCAN
-- │ limit: 5000
-- │
-- └── • scan
-- table: parent@parent_pkey
-- spans: FULL SCAN
Without the NOT NULL constraint, it’s possible that some rows in the child table have a NULL parent_id, and therefore will not have corresponding rows in the parent table. These child rows are filtered out by the join condition. The limit cannot be pushed down below the join because it could prematurely ignore child rows with corresponding parent rows in favor of child rows without parent rows, producing an incorrect result. For example, imagine that we did push down the limit into the scan, and of the first 5000 child rows scanned, one has a NULL parent_id. Also, imagine that there exists another child row with a non-NULL parent_id that is not scanned. Only 4999 of the scanned children would pass the join condition, and therefore only 4999 children would be included in the query result, rather than all 5,000 that should be returned.
The NOT NULL constraint ensures that all of the child rows have parent rows. Therefore, it is safe to push the limit into the left side of the join because all rows scanned in the child table are guaranteed to pass the join condition.
Decorrelating foreign-key joins
A NOT NULL constraint can also aid the optimizer in decorrelating a foreign-key join, i.e., transforming a correlated join into an uncorrelated join. A correlated join is a join where one of the join’s inputs has references to columns produced by the other join input. Consider the tables below which are similar to the tables in the last example.
-- Create a parent table with 1000 rows.
CREATE TABLE parent (
id UUID PRIMARY KEY,
v INT
);
INSERT INTO parent
SELECT gen_random_uuid(), i
FROM generate_series(1, 1000) g(i);
-- Create 100 child rows for each parent row.
CREATE TABLE child (
id UUID PRIMARY KEY,
v INT,
parent_id UUID REFERENCES parent(id)
);
INSERT INTO child
SELECT gen_random_uuid(), i, parent.id
FROM parent, generate_series(1, 100) g(i);
-- Collect table statistics.
ANALYZE parent;
ANALYZE child;
In the query below, notice that the subquery references columns from outside the subquery, namely, child.parent_id and child.v. The optimizer plans this query with a left-apply-join, which operates like a relational for-each loop. For every input row, the left-apply-join replaces the outer column references of the subquery with constant values from the input row, re-optimizes the subquery, and executes it. The overhead for each input row is significant, and apply-joins are terribly inefficient compared to other types of join operators. Notice the 725 millisecond execution latency of the query.
EXPLAIN ANALYZE
SELECT
id,
(SELECT p.v + c.v FROM parent AS p WHERE id = c.parent_id) AS total_v
FROM child AS c
LIMIT 1000;
-- info
-- ------------------------------------------
-- planning time: 419µs
-- execution time: 725ms
-- • render
-- │
-- └── • limit
-- │ count: 1000
-- │
-- └── • apply join (left outer)
-- │ pred: id = parent_id
-- │
-- └── • scan
-- table: child@child_pkey
-- spans: FULL SCAN
Once again, let’s add a NOT NULL constraint to child.parent_id.
ALTER TABLE child ALTER COLUMN parent_id SET NOT NULL;
The optimizer can now replace the left-apply-join with a much more efficient hash-join, and the execution latency plummets to 2 milliseconds.
EXPLAIN ANALYZE
SELECT
id,
(SELECT p.v + c.v FROM parent AS p WHERE id = c.parent_id) AS total_v
FROM child AS c
LIMIT 1000
-- info
-- ------------------------------------------
-- planning time: 294µs
-- execution time: 2ms
--
-- • render
-- │
-- └── • hash join
-- │ equality: (parent_id) = (id)
-- │ right cols are key
-- │
-- ├── • scan
-- │ table: child@child_pkey
-- │ spans: LIMITED SCAN
-- │ limit: 1000
-- │
-- └── • scan
-- table: parent@parent_pkey
-- spans: FULL SCAN
Just as in the previous example, the NOT NULL constraint guarantees that each row in the child table will have a corresponding row in the parent table. With this assurance, the optimizer performs a series of transformations starting with converting the left-apply-join into an inner-apply-join. The NOT NULL constraint confirms that there will be no NULL-extended rows as a result of the left-apply-join, so it’s equivalent to an inner-apply-join.
Next, the optimizer decorrelates the inner-apply-join. At a high level, the join is decorrelated by pulling the filter WHERE id = c.parent_id above the join. Before decorrelation, the query plan looks like this:
• render
│
└── • limit
│ count: 1000
│
└── • apply join (inner)
│ pred: true
│
├── • scan
│ table: child@child_pkey
│ spans: FULL SCAN
│
└── • filter
│ filter: id = parent_id
│
└── • scan
table: parent@parent_pkey
spans: FULL SCAN
After decorrelation, the filter is above the join.
• render
│
└── • limit
│ count: 1000
│
└── • filter
│ filter: id = parent_id
│
└── • apply join (inner)
│ pred: true
│
├── • scan
│ table: child@child_pkey
│ spans: FULL SCAN
│
└── • scan
table: parent@parent_pkey
spans: FULL SCAN
This is significant because it means that the right child of the apply-join no longer references columns produced by the right child of the join. Therefore the join is no longer correlated, and it can be trivially converted into a non-apply join.
After decorrelation, the NOT NULL constraint allows for an additional optimization. The limit is pushed into the left side of the join, exactly as described in the first example. Without the guarantee provided by the NOT NULL constraint, the initial transformation from a left-apply-join into an inner-apply-join is not possible, halting this chain of optimizations before it can even get started.
Further optimizations
In the contrived examples above, it’s not obvious that these optimizations would apply in real-world queries. However, it’s important to remember that transformations like these work together in concert with hundreds of other possible transformations. As shown in the last example, a single transformation can cascade into numerous other transformations that drastically optimize the query plan. It’s these complex interactions between transformations that make query optimizers powerful, and, when they produce a surprisingly efficient query plan, delightful too.
